package com.leecode;

import com.test.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 236. 二叉树的最近公共祖先
 *
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x
 * 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 * 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
 *
 * 示例 1:
 *
 * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 * 输出: 3
 * 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
 *
 * 示例 2:
 *
 * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 * 输出: 5
 * 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
 *
 * 说明:
 *     所有节点的值都是唯一的。
 *     p、q 为不同节点且均存在于给定的二叉树中。
 */
public class Leet236 {
	public static void main(String[] args) {
		TreeNode root=new TreeNode(2);
		TreeNode left = new TreeNode(1);
		root.left=left;
		TreeNode right = new TreeNode(3);
		root.right=right;
		new Leet236().lowestCommonAncestor(root,left,root);
	}

	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		List<TreeNode> list=new ArrayList();
		dfsHash(root,p,list);
		for (int i = 0; i < list.size(); i++) {
			if (dfsHash(list.get(i), q, new ArrayList())) {
				return list.get(i);
			}
		}
		return null;
	}
	/**
	 * dfs+hash
	 */
	public boolean dfsHash(TreeNode root, TreeNode target, List<TreeNode> list) {
		if(root==null)return false;
		if(root==target){
			list.add(target);
			return true;
		}

		if(dfsHash(root.left,target,list)){
			list.add(root);
			return true;
		}
		if(dfsHash(root.right,target,list)){
			list.add(root);
			return true;
		}
		return false;
	}


}
